package 双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*力扣 18题*/
/*在数组中找出 nums[a]+nums[b]+nums[c]+nums[d] == target 顺序可以乱但是，元组不可重复
* 解题思路：1.依次固定一个数a，在a后面的区间内利用三数之和 找到三个数，使者三个数的和等于target-a即可
*          2. 依次固定数b，b的后面区间利用双指针找到两个数，使两数之和等于target-a-b即可
* 细节：1.不重复2.不漏*/
public class 四数之和 {
    public List<List<Integer>> fourSum(int [] nums,long target){
        int n =nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        if(nums == null || n<4){
            return ret;//优化节省时间
        }
        for(int i =0;i<n;){//固定数a

            for(int j=i+1;j<n;){//固定数b
               long need=target-nums[i]-nums[j];
                int left = j+1,right=n-1;//双指针

                while(left<right){
                   long sum = nums[left]+nums[right];
                    if(sum == need){
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;right--;
                        //去重一
                        while(left<right&&nums[left] == nums[left-1]) left++;
                        while (left<right && nums[right]==nums[right+1]) right--;
                    }else if(sum > need){
                        right--;
                    }else{
                        left++;
                    }
                }
                j++;
                //去重二
                while(j<n && nums[j] == nums[j-1]) j++;
            }
            i++;
            // 去重三
            while (i<n&&nums[i] == nums[i-1]) i++;
        }

        return  ret;
    }
}
